The present invention relates to digital data networks. More particularly, the present invention relates to an apparatus and method for improving communication among devices that are coupled to Asynchronous Transfer Mode (ATM) digital data networks.
Asynchronous Transfer Mode is an emerging technology in the fields of telecommunication and computer networking. ATM permits different types of digital information (e.g., computer data, voice, video, and the like) to intermix and transmit over the same physical medium (i.e., copper wires, fiber optics, wireless transmission medium, and the like). ATM works well with data networks, e.g., the Internet, wherein digital data from a plurality of communication devices such as video cameras, telephones, television sets, facsimile machines, computers, printers, and the like, may be exchanged.
To facilitate discussion, FIG. 1 illustrates a prior art data network 3, including ATM switches 5 and 10 and a plurality of communication devices 22–24, 32, 42–44, 52, 62–63, 72–74 and 82–85. ATM switches 5 and 10 may represent a digital switch for coupling, for either bidirectional or unidirectional transmission, two or more of the communication devices together for communication purpose and may represent a data network such as a local area network (LAN), a wide area network (WAN), or the global data network popularly known as the Internet.
Each communication device 22–24, 42–44, 52, 62–63, 72–74 and 82–85 can be part of smaller networks 21, 41, 51, 61, 71 and 81, and coupled to ATM switch 5 or 10 through input and output ports and physical connections 20, 40, 50, 60, 70 or 80. A communication device, such as video server 32, can also be connected directly to the ATM switch through a physical connection 30. The smaller networks or the ATM switches may include circuitry to translate data from the communication devices into an ATM data format for transmission via the ATM switches, and to translate ATM data transmitted via the ATM switches into data formats compatible with the communication devices.
Irrespective of the source, data is transformed into an ATM data format prior to being transmitted via an ATM-enabled network. As is well known, a typical ATM data cell 2 includes a header portion and a data portion. Cell header portion may include information regarding the type of information being encapsulated in the ATM data cell, e.g., the destination for that information, and the like. Cell data portion typically includes the information being sent. By standardizing the format of the ATM cells, information from different communication devices may be readily intermixed and transmitted irrespective of its original format.
In the implementation of ATM technology in a data network, the challenge has been to improve the efficiency with which ATM switches 5 and 10 handle multiple simultaneous connections among the multiple communication devices. For peak efficiency, it is generally desirable to have an ATM switch transmit at the highest bandwidth that the network can handle, while at the same time minimizing delay and maximizing data integrity. Unfortunately, the high bandwidth demanded by such a design generally results in a prohibitively expensive ATM switch.
The standards for ATM networks have required that ATM switches be capable of a certain level of quality of service (QoS). For example, the ATM Forum Technical Committee has published a Traffic Management Specification, version 4.0, April 1996, which lays out the specifications for quality of service, which is incorporated herein by reference for all purposes. Some of the criteria of QoS include Peak-to-Peak Cell Delay Variation (peak-to-peak CDV), Maximum Cell Transfer Delay (maxCTD), Cell Loss Rate (CLR), Cell Error Ratio (CER), Severely Errored Cell Block Ratio (SECBR) and Cell Misinsertion Rate (CMR), as well as other characteristics of a connection. Additionally, each connection may be classified as certain types of connections, including constant bit rate, real time variable bit rate, non-real time variable bit rate, unspecified bit rate and available bit rate. Each type of classification requires a certain QoS criteria.
The QoS criteria must be met by all ATM networks and switches. At the same time it is recommended that traffic shaping be performed in order to maximize the efficiency of any given connection. Traffic shaping alters the characteristics of a stream of cells to best fully utilize the capabilities of the connection.
Referring back to FIG. 1, a user may wish to use telephone 22 to communicate with telephone 85. Telephone 22 begins to transmit cells 2 with the appropriate header and body. Among the cells 2 are resource management (RM) cells 2′ (not shown). Resource cells 2′ are sent out through the ATM network 3 and is eventually returned to either ATM switch 5 or network 21, which ever is sending the cells in an ATM format. The resource cell informs the switch, in this case ATM switch 5, about the characteristics of the connection between telephone 22 and telephone 85. The connection formed between the telephones 22 and 85 is a virtual circuit (VC) since it is formed from a myriad of potential circuits throughout the vast network and is not a permanent physical connection. The physical pathway, or a logical grouping of virtual circuits, used to form the virtual connection are virtual paths (VP).
The VC from telephone 22 consists partly of network 21, physical connection 20 and ATM switch 5. ATM switch 5 and ATM switch 10 are linked through physical connections 12 and 13. Between these connections 12 and 13 there can be any number of other switches, networks and connections through which the VC is connected. From ATM switch 10 the VC continues through physical connection 80, network 81 and finally to telephone 85.
Traffic shaping is desired because the characteristics of the VC should be considered in order to fully utilize the particular VC. For example, telephone 22 may need to communicate with telephone 85 at 64 kbps at a constant bit rate since voice communication is typically constant. Connections 12 and 13 between ATM switches 5 and 10 are typically capable of handling high bandwidth communications in the order of 45 Mbps or more. However, connections 20 and 80 may be more limited. In many cases, connections between a network and an ATM switch may be 1.544 Mbps. Still, 1.544 Mbps is great enough to handle the virtual connection between telephone 22 and telephone 85. But, one reason for traffic shaping is to fully utilize the 45 Mbps connections 12 and 13 rather than tying up the high bandwidth connections with only the 64 kbps transmissions.
In another example, video server 32 may wish to communicate with television 82 at a non-real time variable bit rate. The video server and connection 30 may be capable of transmitting at up to 30 Mbps. However, connection 80 may be only capable of handling 1.544 Mbps, and cannot handle 30 Mbps communications. Thus, the output of the video server should be shaped to communicate at 1.544 Mbps.
A bottleneck may occur when both telephone 22 and video server 32 are communicating with telephone 85 and television 82 at the same time, respectively. Therefore, traffic shaping is required to ensure that only a maximum of 1.544 Mbps is being transmitted to network 81, otherwise information may be corrupted or lost, and thus QoS standards not met.
In the prior art, many ATM techniques of traffic shaping have been proposed to efficiently use the ATM network while still meeting QoS criteria. One practice condoned by the ATM forum has been to not utilize any traffic shaping, and simply ensure that QoS criteria have been met. As can be appreciated, this approach while simplistic and less expensive than traffic shaping, fails to properly utilize the full potential of an ATM network.
FIG. 2 is a block diagram of a prior art method of traffic shaping implemented in an ATM switch. In this figure and the figures that follow, a convention has been adopted for ease of illustration and understanding. It is assumed herein that ATM connections on the left side of a depicted ATM switch represent ATM input connections. Contrarily, ATM ports illustrated on the right side of a depicted ATM switch represent ATM output connections. In reality, most ATM ports are bidirectional and may be disposed at any location relative to the ATM switch. Furthermore, although only a few ATM connections are shown herein, the number of ATM connections coupled to a given ATM switch is theoretically unlimited. Accordingly, the convention is employed to facilitate discussion only and is not intended to be limiting in anyway.
Typically, the prior art method of traffic shaping implements a traffic shaper 95 for every VC queue 92. A VC queue has a queue of cells associated with a particular VC. Generally, an ATM switch sorts the incoming cells from the various connections and groups them by their respective VC. For example, the cells that are part of the communication from telephone 22 to telephone 85 can be grouped together in VC queue 92(5). And, cells from video server 32 to television 82 can be grouped in VC queue 92(1). The cells of a VC queue are typically ordered by the sequence at which they arrived at the ATM switch.
The cells arrive at the traffic shapers where they wait for eventual transmission by router 97. The traffic shapers trickle out the cells to the router based upon certain criteria. One criteria may be data rate. Typically, a VC having a higher data rate requirement than another is allowed to trickle out more cells per time period than a VC with a lower data rate requirement. Thus, the traffic shapers trickle out cells at different rates. The cells are grouped together into a continuous stream of cells by router 97, typically to fully utilize the bandwidth of output connection 12.
The traffic shaper method may help to fully utilize high bandwidth output connection 12, but the method requires a traffic shaper for every VC queue. Implementing a traffic shaper for every virtual connection established by an ATM switch can be prohibitively computationally intensive, and therefore expensive and overly complex. Further, the prior art method may not fully alleviate the situation of overloading a lower bandwidth connection further downstream in the virtual path.
FIG. 3a is a block diagram of a prior art timing chain method of traffic shaping implemented in an ATM switch. In the timing chain method the cells of the VC queues 92 are scheduled by timing chain router 99 based upon the data rate of the particular VC queue.
FIGS. 3b and 3c are block diagrams of an implementation of a prior art timing chain router 99. The cells of the various VC queues arrive at the left side of the timing chain router 99. In the example, timing chain router 99 receives cells from five different VC queues. The cells are labeled a–e for VC queues A–E (not shown).
Typically, timing chain router 99 prepares a number of packets 100(0)–100(9) to send in the next time interval. By way of example, if the output data rate of timing chain 99 is equivalent to 10 packets per millisecond, timing chain router 99 may prepare the next 10 packets to send in the next millisecond.
The VCs may have different data rates and priorities. In this example of a typical timing chain algorithm, VCs A and B may be of equal priority with a data rate of 2 cells per millisecond. VCs C, D and E may be of equal priority, lower than the priority of VCs A and B, VC C requiring 4 cells per millisecond, and VCs D and E requiring 1 cell per millisecond. Under these assumptions timing chain router 99 may sort the cells from VC queues A–E in a first sort 100.
The first sort 100(0) was able to accommodate the priorities and data rates of all the VCs. Typically, timing chain router 99 would have provided cell slots 100(0)–(9) to VC queues A and B because of their higher priority. Timing chain router 99 assigns cell slots 100(0)–(9) according to the arrival times of the cells and the next available cell slot 100(0)–(9). The sequence of cells 100 may have occurred as illustrated if some “c” cells were already present and the “a” and “b” cells arrived later and placed in the earliest open cell slots 100(0), (1), (4) and (5). Finally, cells “d” and “e” were placed in the remaining slots 100(8) and (9). Fortunately, enough cell slots were available to accommodate all the VC queues.
FIG. 3c depicts a second sort 100′ of cell slots 100(0)–(9). If anew VC A′ is established with the same data rate and priority as A the a′ cells must be inserted into the sort 100. In the new sort 100′ the a′ cells displace cells of lower priority. In the example, the “c” cells are pushed back and the “d” and “e” cells are completely removed from the new sort 100′. Using the timing chain method almost the entire sort 100 had to be reordered in order to accommodate the new VC. Typically, a timing chain is significantly longer than the illustrative example. Additionally, the timing chain becomes more complex as the output data rate of the timing chain is increased. Thus, typical timing chain routers require a large amount of computational power to continually reorganize the timing chain.
Thus, the use of a timing chain method is overly complex. Using the timing chain method requires resorting of cells, which is generally complicated and requires a large amount of computational resources. Additionally, the timing chain method is unpredictable. As in the case of the example VCs D and E may have been delayed, terminated or rerouted. Typically, VCs D and E may be required to establish a new VC using a different route, however, an interruption in the connection may have occurred. Also, VC C may have been interrupted instead of VCs D and E.
As can be appreciated from the foregoing, ATM switch designers are constantly searching for ways to improve switch performance and to lower implementation cost. Particularly, there are desired improved ATM switching architectures and methods therefor that advantageously maximize the efficiency of ATM cell transmission for multiple simultaneous connections. The desired ATM switching architectures and methods therefor preferably include structures and techniques for effectively shaping the output traffic of an ATM device while meeting QoS criteria, thereby maximizing performance of an ATM output device.